<!DOCTYPE html>
<html lang=zh>
<head><meta name="generator" content="Hexo 3.9.0">
    <!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="description" content="机器学习中的“hello world!”就像我们学习编程语言一样，我们的第一个尝试就是在终端命令行中输出的 “Hello World”。机器学习中的 “Hello World” 便是识别手写字数据集。想想在得到一张手写数字图片的数据之后如何分析出正确的数字？keras-js 的实际 demo 数据的表示和收集图片其实放大来看其实就是一个个像素点，对于黑白图像，每个像素点就只有黑白两种颜色以及黑白">
<meta name="keywords" content="javascript,人工智能">
<meta property="og:type" content="article">
<meta property="og:title" content="人工智能入门---使用js实现k近邻算法">
<meta property="og:url" content="https://andyliwr.github.io/2018/01/09/js_knn_algorithm/index.html">
<meta property="og:site_name" content="月光倾城的代码小屋">
<meta property="og:description" content="机器学习中的“hello world!”就像我们学习编程语言一样，我们的第一个尝试就是在终端命令行中输出的 “Hello World”。机器学习中的 “Hello World” 便是识别手写字数据集。想想在得到一张手写数字图片的数据之后如何分析出正确的数字？keras-js 的实际 demo 数据的表示和收集图片其实放大来看其实就是一个个像素点，对于黑白图像，每个像素点就只有黑白两种颜色以及黑白">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai.png">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai1.png/default">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai2.png/default">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai3.png">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/a4.png">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai5.png">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai7.png">
<meta property="og:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai6.png">
<meta property="og:updated_time" content="2020-01-15T06:30:09.116Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="人工智能入门---使用js实现k近邻算法">
<meta name="twitter:description" content="机器学习中的“hello world!”就像我们学习编程语言一样，我们的第一个尝试就是在终端命令行中输出的 “Hello World”。机器学习中的 “Hello World” 便是识别手写字数据集。想想在得到一张手写数字图片的数据之后如何分析出正确的数字？keras-js 的实际 demo 数据的表示和收集图片其实放大来看其实就是一个个像素点，对于黑白图像，每个像素点就只有黑白两种颜色以及黑白">
<meta name="twitter:image" content="https://file.lantingshucheng.com/blog/2018_01_09/ai.png">
    
    
        
          
              <link rel="shortcut icon" href="/images/favicon.ico">
          
        
        
          
            <link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
          
        
        
          
            <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
          
        
    
    <!-- title -->
    <title>人工智能入门---使用js实现k近邻算法</title>
    <!-- styles -->
    <link rel="stylesheet" href="/css/style.css">
    <!-- persian styles -->
    
      <link rel="stylesheet" href="/css/rtl.css">
    
    <!-- rss -->
    
    
</head>

<body class="max-width mx-auto px3 ltr">
    
      <div id="header-post">
  <a id="menu-icon" href="#"><i class="fas fa-bars fa-lg"></i></a>
  <a id="menu-icon-tablet" href="#"><i class="fas fa-bars fa-lg"></i></a>
  <a id="top-icon-tablet" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');" style="display:none;"><i class="fas fa-chevron-up fa-lg"></i></a>
  <span id="menu">
    <span id="nav">
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a href="/search/">搜索</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/others/">其他文章</a></li>
        
      </ul>
    </span>
    <br/>
    <span id="actions">
      <ul>
        
        <li><a class="icon" href="/2018/01/10/ps_cutterman/"><i class="fas fa-chevron-left" aria-hidden="true" onmouseover="$('#i-prev').toggle();" onmouseout="$('#i-prev').toggle();"></i></a></li>
        
        
        <li><a class="icon" href="/2018/01/09/array_unknow_function/"><i class="fas fa-chevron-right" aria-hidden="true" onmouseover="$('#i-next').toggle();" onmouseout="$('#i-next').toggle();"></i></a></li>
        
        <li><a class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up" aria-hidden="true" onmouseover="$('#i-top').toggle();" onmouseout="$('#i-top').toggle();"></i></a></li>
        <li><a class="icon" href="#"><i class="fas fa-share-alt" aria-hidden="true" onmouseover="$('#i-share').toggle();" onmouseout="$('#i-share').toggle();" onclick="$('#share').toggle();return false;"></i></a></li>
      </ul>
      <span id="i-prev" class="info" style="display:none;">上一篇</span>
      <span id="i-next" class="info" style="display:none;">下一篇</span>
      <span id="i-top" class="info" style="display:none;">返回顶部</span>
      <span id="i-share" class="info" style="display:none;">分享文章</span>
    </span>
    <br/>
    <div id="share" style="display: none">
      <ul>
  <li><a class="icon" href="http://www.facebook.com/sharer.php?u=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/"><i class="fab fa-facebook " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://twitter.com/share?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&text=人工智能入门---使用js实现k近邻算法"><i class="fab fa-twitter " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.linkedin.com/shareArticle?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-linkedin " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://pinterest.com/pin/create/bookmarklet/?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&is_video=false&description=人工智能入门---使用js实现k近邻算法"><i class="fab fa-pinterest " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=人工智能入门---使用js实现k近邻算法&body=Check out this article: https://andyliwr.github.io/2018/01/09/js_knn_algorithm/"><i class="fas fa-envelope " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://getpocket.com/save?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-get-pocket " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://reddit.com/submit?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-reddit " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.stumbleupon.com/submit?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-stumbleupon " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://digg.com/submit?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-digg " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.tumblr.com/share/link?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&name=人工智能入门---使用js实现k近邻算法&description="><i class="fab fa-tumblr " aria-hidden="true"></i></a></li>
</ul>

    </div>
    <div id="toc">
      <ol class="toc"><li class="toc-item toc-level-4"><a class="toc-link" href="#机器学习中的“hello-world-”"><span class="toc-number">1.</span> <span class="toc-text">机器学习中的“hello world!”</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#数据的表示和收集"><span class="toc-number">2.</span> <span class="toc-text">数据的表示和收集</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#准备数据"><span class="toc-number">3.</span> <span class="toc-text">准备数据</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#选择一种算法"><span class="toc-number">4.</span> <span class="toc-text">选择一种算法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#k-近邻算法概述"><span class="toc-number">5.</span> <span class="toc-text">k-近邻算法概述</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#k-近邻算法实现"><span class="toc-number">6.</span> <span class="toc-text">k-近邻算法实现</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#测试算法"><span class="toc-number">7.</span> <span class="toc-text">测试算法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#使用算法"><span class="toc-number">8.</span> <span class="toc-text">使用算法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#进一步思考"><span class="toc-number">9.</span> <span class="toc-text">进一步思考</span></a></li></ol>
    </div>
  </span>
</div>

    
    <div class="content index py4">
        
        <article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  <header>
    
    <h1 class="posttitle" itemprop="name headline">
        人工智能入门---使用js实现k近邻算法
    </h1>



    <div class="meta">
      <span class="author" itemprop="author" itemscope itemtype="http://schema.org/Person">
        <span itemprop="name">月光倾城的代码小屋</span>
      </span>
      
    <div class="postdate">
        <time datetime="2018-01-09T22:49:15.000Z" itemprop="datePublished">2018-01-09</time>
    </div>


      

      
    <div class="article-tag">
        <i class="fas fa-tag"></i>
        <a class="tag-link" href="/tags/javascript/">javascript</a>, <a class="tag-link" href="/tags/人工智能/">人工智能</a>
    </div>


    </div>
  </header>
  

  <div class="content" itemprop="articleBody">
    <p><img src="https://file.lantingshucheng.com/blog/2018_01_09/ai.png" alt="手写数字识别"></p>
<h4 id="机器学习中的“hello-world-”"><a href="#机器学习中的“hello-world-”" class="headerlink" title="机器学习中的“hello world!”"></a>机器学习中的“hello world!”</h4><p>就像我们学习编程语言一样，我们的第一个尝试就是在终端命令行中输出的 “Hello World”。机器学习中的 “Hello World” 便是识别手写字数据集。<br><img src="https://file.lantingshucheng.com/blog/2018_01_09/ai1.png/default" alt="数字"><br>想想在得到一张手写数字图片的数据之后如何分析出正确的数字？<br><a href="https://transcranial.github.io/keras-js/#/mnist-cnn" target="_blank" rel="noopener">keras-js 的实际 demo</a></p>
<h4 id="数据的表示和收集"><a href="#数据的表示和收集" class="headerlink" title="数据的表示和收集"></a>数据的表示和收集</h4><p>图片其实放大来看其实就是一个个像素点，对于黑白图像，每个像素点就只有黑白两种颜色以及黑白深度的区别，怎样用一种程序的方式来表达一张白底黑字的图像的像素点分布以及它的黑白深度呢？<br><img src="https://file.lantingshucheng.com/blog/2018_01_09/ai2.png/default" alt="图形的表示"><br>如何将一张图转化成深度矩阵的格式是图像识别要做的，这是另一个广泛的课题，这里不展开。我们直接使用<a href="http://yann.lecun.com/exdb/mnist/" target="_blank" rel="noopener">MNIST 的数据集</a>，它的数据表示方式正如上面所描述的那样，只是 MNIST 数据集中每一张图片是包含 28 * 28 个像素点的。</p>
<p>确定了数据的表示方式，接下来我们还需要对每个数据的实际含义进行标识。</p>
<p>回想一下我们自己是如何认识这些数字的？即我们是怎样认定图像中的 1 形状表示的就是数字 1？————事物的认识。认知是由他人（数学老师教的，告诉我们这样是 1，这样是 2）教育的。</p>
<p>为了收集训练数据，我们可以随机找人在手写识别程序中画数字，然后标识它的结果，最终以任何的形式（文本、表格…）储存。以手写字为例，我们可以用文本的方式存储，格式可以是这样：</p>
<figure class="highlight angelscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0.3</span> <span class="number">0</span> <span class="number">1</span> <span class="number">0</span> ... n(=<span class="number">28</span>) | <span class="number">4</span></span><br><span class="line"><span class="number">1</span> <span class="number">0</span> <span class="number">0.1</span> <span class="number">0</span> <span class="number">0</span> <span class="number">0</span> ... n(=<span class="number">28</span>) | <span class="number">6</span></span><br><span class="line">....</span><br><span class="line">n(=<span class="number">1000</span>)</span><br></pre></td></tr></table></figure>
<p>其中每一行代表一个训练数据（一个 MNIST 数据，有多少行表示有多少个数据），使用 “|” 分割数据的表示和它对应的数字。</p>
<p>在本文中我们将直接使用 MNIST 数据集，因此如何收集数据在这里不再展开。<strong>在机器学习中经常会使用公开的数据集来进行训练和测试</strong>。</p>
<p>通过确定数据的表示和收集，我们可以了解到的是：</p>
<ul>
<li>数据是一切机器学习的基础；</li>
<li>训练数据的好坏将会影响到我们机器学习算法预测的准确率：<ul>
<li>想象一下如果某些数据我们标识错误，把 1 标识成 2；</li>
<li>想象一下如果训练数据中有大量的重复值，或某个数字的数据量特别大而另外一些数字的数据量很小。</li>
</ul>
</li>
</ul>
<h4 id="准备数据"><a href="#准备数据" class="headerlink" title="准备数据"></a>准备数据</h4><p>我们收集到的数据可能会以任何的一种形式存储，例如文本、表格、二进制文件等等。MNIST 数据集是使用二进制存储的，因此在程序中我们需要将它转换为 Javascript 比较容易操作的的数据格式，例如数组。</p>
<p>本文中我们将使用一个 NPM 包 <a href="https://github.com/cazala/mnist" target="_blank" rel="noopener">mnist</a> 提供的，已经转换好的数据，它的格式如下：</p>
<figure class="highlight angelscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">[</span><br><span class="line">  &#123;</span><br><span class="line">    input: [<span class="number">0</span>, <span class="number">0.4</span>, <span class="number">0.5</span>, <span class="number">0</span>, <span class="number">0.1</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, ..., n], <span class="comment">// n = 728</span></span><br><span class="line">    output: [<span class="number">0</span>, <span class="number">1</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>], <span class="comment">// 1</span></span><br><span class="line">  &#125;,</span><br><span class="line">  &#123;</span><br><span class="line">    input: [<span class="number">1</span>, <span class="number">0.4</span>, <span class="number">0.5</span>, <span class="number">0</span>, <span class="number">0.8</span>, <span class="number">0</span>, <span class="number">0.1</span>, <span class="number">0</span>, <span class="number">1</span>, ..., n], <span class="comment">// n = 728</span></span><br><span class="line">    output: [<span class="number">0</span>, <span class="number">0</span>, <span class="number">1</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>], <span class="comment">// 2</span></span><br><span class="line">  &#125;,</span><br><span class="line">  ....</span><br><span class="line">]</span><br></pre></td></tr></table></figure>
<p><strong>PS</strong>: 这里不知道是不是写错了，28*28 应该是 784，总之意思呢，就是 input 是 MNIST 的一个数据，output 是这个数据表示的数字，采用了一种叫做<a href="https://www.jianshu.com/p/00f2affe553a" target="_blank" rel="noopener">One-Hot</a>的编码方式，表达方式有点怪，有点像二进制，第一项为 1 的话就是 0，第二项为 1 的话就是 1，依次类推…</p>
<h4 id="选择一种算法"><a href="#选择一种算法" class="headerlink" title="选择一种算法"></a>选择一种算法</h4><p>通过上面的数据准备，我们已经把一个现实中的问题转化成了一个数学问题：给定 728 个 0 到 1 之间数值的特征，应该将它分类到 0 ~ 9 哪个数字中？</p>
<p>这就是机器学习中的主要任务——分类。有很多的机器学习算法可以用来解决分类问题，文本将使用 k-近邻算法<a href="https://zh.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E9%84%B0%E5%B1%85%E6%B3%95" target="_blank" rel="noopener">k-NN</a>来解决这个问题，因为它非常有效且容易理解。</p>
<h4 id="k-近邻算法概述"><a href="#k-近邻算法概述" class="headerlink" title="k-近邻算法概述"></a>k-近邻算法概述</h4><p>在一个 10 * 10 的二维平面内画一条线把它分成 2 个区域(A/B)。假设我们不知道线是如何画的，但现已知有 4 个点，a 点坐标是 (1, 1) 属于区域 A，b 点坐标是 (2, 2) 属于区域 A，c 点坐标是 (9, 9) 属于区域 B，d 点坐标是 (8, 8) 属于区域 B。这时候再给定一个 e 点坐标是 (8.5, 8.5) ，请问它最有可能在哪个区域内？<br><img src="https://file.lantingshucheng.com/blog/2018_01_09/ai3.png" alt="matlab"></p>
<p>绝大多数人都会说“可能是 B”。我们是如何得出这个答案的？——因为它和 c, d “看起来更接近一些，更有可能在同一个区域”。同样的推论可以延伸至三维、四维甚至更多维度的数据中。MNIST 的数据表示就是 728 个特征的多纬数据，k-近邻算法同样适用。</p>
<blockquote>
<p>存在一个训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本特征最近邻的分类标签。一般来说，我们只选择样本数据集中前 k 个最相似的数据，这就是 k-近邻算法的 k 的出处。<br>——《机器学习实战》k 近邻算法</p>
</blockquote>
<p>两个向量之间的距离可以通过欧几里得距离公式求得：<br><img src="https://file.lantingshucheng.com/blog/2018_01_09/a4.png" alt="欧几里得距离公式"></p>
<h4 id="k-近邻算法实现"><a href="#k-近邻算法实现" class="headerlink" title="k-近邻算法实现"></a>k-近邻算法实现</h4><p>我们来使用 js 来实现 k-近邻算法（ps: 加了点注释，方便大家理解）<br><img src="https://file.lantingshucheng.com/blog/2018_01_09/ai5.png" alt="算法分析"></p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * k-近邻算法函数</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;Object&#125;</span> </span>x 目标点的坐标，值类似与这种 [0, 0.4, 0.5, 0, 0.1, 0, 0, 0, 0, ..., n]</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;Array&#125;</span> </span>trainingData 训练数据，是一个二维数组，数组中每一项和x的格式差不多</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;Array&#125;</span> </span>labels 结果集，trainingData的每一项在labels中都会有一个值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;Number&#125;</span> </span>k 人为定义的参数，就是选择样本数据集中前 k 个最相似的数据，后期可以通过调整来提高精确率</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">classify</span>(<span class="params">x, trainingData, labels, k</span>) </span>&#123;</span><br><span class="line">  <span class="comment">// 确定目标点 x 与训练数据中每个点的距离（欧几里得距离公式）</span></span><br><span class="line">  <span class="keyword">const</span> distances = [];</span><br><span class="line">  trainingData.forEach(<span class="function"><span class="params">element</span> =&gt;</span> &#123;</span><br><span class="line">    <span class="keyword">let</span> distance = <span class="number">0</span>;</span><br><span class="line">    element.forEach(<span class="function">(<span class="params">value, index</span>) =&gt;</span> &#123;</span><br><span class="line">      <span class="keyword">const</span> diff = x[index] - value;</span><br><span class="line">      distance += diff * diff;</span><br><span class="line">    &#125;);</span><br><span class="line">    distances.push(<span class="built_in">Math</span>.sqrt(distance));</span><br><span class="line">  &#125;);</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 将训练数据按照与 x 点的距离从近到远排序</span></span><br><span class="line">  <span class="keyword">const</span> sortedDistIndicies = distances</span><br><span class="line">    <span class="comment">// 这一步是将距离数组转化成[&#123;value: xxx, index: xxx&#125;...]的格式，因为index属性后面会用到</span></span><br><span class="line">    .map(<span class="function">(<span class="params">value, index</span>) =&gt;</span> &#123;</span><br><span class="line">      <span class="keyword">return</span> &#123; value, index &#125;;</span><br><span class="line">    &#125;)</span><br><span class="line">    .sort(<span class="function">(<span class="params">a, b</span>) =&gt;</span> a.value - b.value);</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 确定前 k 个点类别的出现频率</span></span><br><span class="line">  <span class="keyword">const</span> classCount = &#123;&#125;;</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; k &gt; i; i++) &#123;</span><br><span class="line">    <span class="comment">// 得到当前距离值对应的label值，也就是在结果集对应的值</span></span><br><span class="line">    <span class="keyword">const</span> voteLabel = labels[sortedDistIndicies[i].index];</span><br><span class="line">    classCount[voteLabel] = (classCount[voteLabel] || <span class="number">0</span>) + <span class="number">1</span>;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 返回出现频率最高的类别作为当前点的预测分类</span></span><br><span class="line">  <span class="keyword">let</span> predictedClass = <span class="string">''</span>;</span><br><span class="line">  <span class="keyword">let</span> topCount = <span class="number">0</span>;</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">const</span> voteLabel <span class="keyword">in</span> classCount) &#123;</span><br><span class="line">    <span class="keyword">if</span> (classCount[voteLabel] &gt; topCount) &#123;</span><br><span class="line">      predictedClass = voteLabel;</span><br><span class="line">      topCount = classCount[voteLabel];</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> predictedClass;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="测试算法"><a href="#测试算法" class="headerlink" title="测试算法"></a>测试算法</h4><p>为了验证我们的算法的效果，我们需要对其进行测试。这就需要引入测试数据。在机器学习中通常会将收集到的数据通过一定的方法划分为训练数据和测试数据然后用于训练和测试。如何划分数据在这里不展开，在本示例中，我们按照 80:20 的比例来划分训练和测试数据，互斥性和随机性由 MNIST 库进行保证。</p>
<p>拿到训练和测试数据后我们就可以对上一步编写的算法进行测试了，我们用错误率来评估算法的可靠性，错误率越低则越可靠：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> classify = <span class="built_in">require</span>(<span class="string">'./kNN'</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 1. 收集数据：忽略，直接使用 MNIST</span></span><br><span class="line"><span class="keyword">const</span> mnist = <span class="built_in">require</span>(<span class="string">'mnist'</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 2. 准备数据</span></span><br><span class="line"><span class="keyword">let</span> trainingImages = [];</span><br><span class="line"><span class="keyword">let</span> labels = [];</span><br><span class="line"></span><br><span class="line"><span class="comment">// 划分数据</span></span><br><span class="line"><span class="keyword">const</span> trainingCount = <span class="number">8000</span>;</span><br><span class="line"><span class="keyword">const</span> testCount = <span class="number">2000</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">set</span> = mnist.<span class="keyword">set</span>(trainingCount, testCount);</span><br><span class="line">const trainingSet = <span class="keyword">set</span>.training;</span><br><span class="line">const testSet = <span class="keyword">set</span>.test;</span><br><span class="line"></span><br><span class="line">// 为我们的 k-NN 算法准备特定的数据格式</span><br><span class="line">trainingSet.forEach((&#123; input, output &#125;) =&gt; &#123;</span><br><span class="line">  <span class="comment">// One-Hot to number</span></span><br><span class="line">  <span class="keyword">const</span> number = output.indexOf(output.reduce(<span class="function">(<span class="params">max, activation</span>) =&gt;</span> <span class="built_in">Math</span>.max(max, activation), <span class="number">0</span>));</span><br><span class="line">  trainingImages.push(input);</span><br><span class="line">  labels.push(number);</span><br><span class="line">&#125;);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 3. 分析数据：在命令行中检查数据，确保它的格式符合要求</span></span><br><span class="line"><span class="built_in">console</span>.log(<span class="string">'trainingImages'</span>, <span class="built_in">JSON</span>.stringify(trainingImages));</span><br><span class="line"><span class="built_in">console</span>.log(<span class="string">'labels'</span>, <span class="built_in">JSON</span>.stringify(labels));</span><br><span class="line"></span><br><span class="line"><span class="comment">// 4. 测试算法</span></span><br><span class="line"><span class="keyword">let</span> errorCount = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">const</span> startTime = <span class="built_in">Date</span>.now();</span><br><span class="line">testSet.forEach(<span class="function">(<span class="params">&#123; input, output &#125;, key</span>) =&gt;</span> &#123;</span><br><span class="line">  <span class="keyword">const</span> number = output.indexOf(output.reduce(<span class="function">(<span class="params">max, activation</span>) =&gt;</span> <span class="built_in">Math</span>.max(max, activation), <span class="number">0</span>));</span><br><span class="line">  <span class="keyword">const</span> predicted = classify(input, trainingImages, labels, <span class="number">3</span>);</span><br><span class="line">  <span class="keyword">const</span> result = predicted == number;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="string">`<span class="subst">$&#123;key&#125;</span>. number is <span class="subst">$&#123;number&#125;</span>, predicted is <span class="subst">$&#123;predicted&#125;</span>, result is <span class="subst">$&#123;result&#125;</span>`</span>);</span><br><span class="line"></span><br><span class="line">  <span class="keyword">if</span> (!result) &#123;</span><br><span class="line">    errorCount++;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;);</span><br><span class="line"></span><br><span class="line"><span class="built_in">console</span>.log(<span class="string">`The total number of errors is: <span class="subst">$&#123;errorCount&#125;</span>`</span>);</span><br><span class="line"><span class="built_in">console</span>.log(<span class="string">`The total error rate is: <span class="subst">$&#123;errorCount <span class="regexp">/ testCount&#125;`);</span></span></span></span><br><span class="line"><span class="string"><span class="subst"><span class="regexp">console.log(`Spend: $&#123;(Date.now() - startTime) /</span> <span class="number">1000</span>&#125;</span>s`</span>);</span><br></pre></td></tr></table></figure>
<p>如无意外，你的终端将会输出这样的结果：<br><img src="https://file.lantingshucheng.com/blog/2018_01_09/ai7.png" alt="运行结果"><br>最终错误率的值大约是 5%。这个结果好吗？并不好。我们可以通过改变 k 的值、改变训练样本的数目影响 k-近邻算法的错误率，读者可以尝试改变这些变量值观察错误率的变化。实际上，只要将 k-近邻算法稍加改良，我们就能够把错误率降到 1% 以下！<br><img src="https://file.lantingshucheng.com/blog/2018_01_09/ai6.png" alt="更多的k-近邻算法"></p>
<p>我们也应该注意到的是，我们的算法在 8000 条训练数据集和 2000 条测试数据集上进行测试，运行了 325 秒！这是一个很差的结果。在实际生产环境中，我们不仅应该关注准确率也应该关注算法的执行效率。</p>
<h4 id="使用算法"><a href="#使用算法" class="headerlink" title="使用算法"></a>使用算法</h4><p>只要测试的算法效果符合预期，我们就可以将算法部署到生产环境进行使用了。我们可以将算法和手写识别程序结合起来，完成一整套获取输入 -&gt; 算法预测 -&gt; 输出结果的流程：首先手写识别程序将用户输入的图像转换为我们期望的数据格式，然后执行我们的算法获取预测的分类。代码可能是这样：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 手写识别程序将用户输入的图像转换为我们期望的数据格式</span></span><br><span class="line"><span class="keyword">const</span> input = [<span class="number">0</span>, <span class="number">0.3</span>, <span class="number">1</span>, <span class="number">1</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0.2</span>, ...];</span><br><span class="line"></span><br><span class="line"><span class="comment">// 执行算法</span></span><br><span class="line">classify(input, trainingImages, labels, <span class="number">3</span>);</span><br></pre></td></tr></table></figure>
<p>很遗憾，在执行算法时我们还是看到了 trainingImages 的存在。这意味着每次预测我们的机器都需要给训练数据准备格外的存储空间。假设训练数据很大（这很常见），则会给我们的生产环境机器造成巨大的内存压力。</p>
<p>每次调用算法还需要传入训练数据的方式即浪费存储空间也不优雅，它只能作为我们的示例进行使用。</p>
<h4 id="进一步思考"><a href="#进一步思考" class="headerlink" title="进一步思考"></a>进一步思考</h4><p>本文我们使用 Javascript 实现了一个非常简单的机器学习算法，并用其来测试 MNIST 数据集，完整代码实现在这个仓库中。这只是一个简单的示例，但从中我们了解到了机器学习的基本概念和解决问题的一般过程。进一步思考，上面的流程中每一步都可能被优化：</p>
<ul>
<li>对于手写字，还有没有其他的数据表示方式？例如我们非要用 0 到 1 的数值来表示点的黑白度吗？</li>
<li>训练数据集是越大越好吗？例如我们将手写字所有的特征排列组合 (28^28) 个数据量作为训练数据集；</li>
<li>如何调整算法参数以获得最佳的收益（准确率和效率）？</li>
</ul>
<p><strong>原文地址</strong>：<a href="http://taobaofed.org/blog/2017/12/07/machine-learning/" target="_blank" rel="noopener">http://taobaofed.org/blog/2017/12/07/machine-learning/</a><br><strong>github 项目地址</strong>: <a href="https://github.com/alvinhui/machine_learning" target="_blank" rel="noopener">https://github.com/alvinhui/machine_learning</a></p>

  </div>
  <div class="statement">
    <hr>  
    1. 如果本文帮到了您，不妨点一下右上角的”<i class="fas fa-share-alt"></i>“按钮。<br>
    2. 除非注明，本博文章均为原创，转载请以链接形式标明本文地址。<br>
    3. 如果你有任何疑问，欢迎发送邮件到我的邮箱<a href="mailto:andyliwr@outlook.com">andyliwr@outlook.com<br>
  </div>
</article>


    <div class="blog-post-comments">
        <div id="gitalk_thread">
            <noscript>加载评论需要在浏览器启用 JavaScript 脚本支持。</noscript>
        </div>
    </div>



        
          <div id="footer-post-container">
  <div id="footer-post">

    <div id="nav-footer" style="display: none">
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a href="/search/">搜索</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/others/">其他文章</a></li>
        
      </ul>
    </div>

    <div id="toc-footer" style="display: none">
      <ol class="toc"><li class="toc-item toc-level-4"><a class="toc-link" href="#机器学习中的“hello-world-”"><span class="toc-number">1.</span> <span class="toc-text">机器学习中的“hello world!”</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#数据的表示和收集"><span class="toc-number">2.</span> <span class="toc-text">数据的表示和收集</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#准备数据"><span class="toc-number">3.</span> <span class="toc-text">准备数据</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#选择一种算法"><span class="toc-number">4.</span> <span class="toc-text">选择一种算法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#k-近邻算法概述"><span class="toc-number">5.</span> <span class="toc-text">k-近邻算法概述</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#k-近邻算法实现"><span class="toc-number">6.</span> <span class="toc-text">k-近邻算法实现</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#测试算法"><span class="toc-number">7.</span> <span class="toc-text">测试算法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#使用算法"><span class="toc-number">8.</span> <span class="toc-text">使用算法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#进一步思考"><span class="toc-number">9.</span> <span class="toc-text">进一步思考</span></a></li></ol>
    </div>

    <div id="share-footer" style="display: none">
      <ul>
  <li><a class="icon" href="http://www.facebook.com/sharer.php?u=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/"><i class="fab fa-facebook fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://twitter.com/share?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&text=人工智能入门---使用js实现k近邻算法"><i class="fab fa-twitter fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.linkedin.com/shareArticle?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-linkedin fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://pinterest.com/pin/create/bookmarklet/?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&is_video=false&description=人工智能入门---使用js实现k近邻算法"><i class="fab fa-pinterest fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=人工智能入门---使用js实现k近邻算法&body=Check out this article: https://andyliwr.github.io/2018/01/09/js_knn_algorithm/"><i class="fas fa-envelope fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://getpocket.com/save?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-get-pocket fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://reddit.com/submit?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-reddit fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.stumbleupon.com/submit?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-stumbleupon fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://digg.com/submit?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&title=人工智能入门---使用js实现k近邻算法"><i class="fab fa-digg fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.tumblr.com/share/link?url=https://andyliwr.github.io/2018/01/09/js_knn_algorithm/&name=人工智能入门---使用js实现k近邻算法&description="><i class="fab fa-tumblr fa-lg" aria-hidden="true"></i></a></li>
</ul>

    </div>

    <div id="actions-footer">
        <a id="menu" class="icon" href="#" onclick="$('#nav-footer').toggle();return false;"><i class="fas fa-bars fa-lg" aria-hidden="true"></i> 菜单</a>
        <a id="toc" class="icon" href="#" onclick="$('#toc-footer').toggle();return false;"><i class="fas fa-list fa-lg" aria-hidden="true"></i> 目录</a>
        <a id="share" class="icon" href="#" onclick="$('#share-footer').toggle();return false;"><i class="fas fa-share-alt fa-lg" aria-hidden="true"></i> 分享</a>
        <a id="top" style="display:none" class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up fa-lg" aria-hidden="true"></i> 返回顶部</a>
    </div>

  </div>
</div>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy; 2020 Dikang Li
  </div>
  <div class="footer-right">
    <nav>
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a href="/search/">搜索</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/others/">其他文章</a></li>
        
      </ul>
    </nav>
  </div>
</footer>

    </div>
</body>
</html>
<!-- styles -->
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<link rel="stylesheet" href="/lib/justified-gallery/css/justifiedGallery.min.css">
<link rel="stylesheet" href="/lib/fancybox/jquery.fancybox.css">

<link rel="stylesheet" href="https://file.lantingshucheng.com/blog/v3/static/styles/gitalk.css">


<!-- jquery -->
<script src="/lib/jquery/jquery.min.js"></script>
<script src="/lib/justified-gallery/js/jquery.justifiedGallery.min.js"></script>
<script src="/lib/fancybox/jquery.fancybox.pack.js"></script>

<script type="text/javascript" src="https://file.lantingshucheng.com/blog/v3/static/scripts/md5.js"></script>
<script type="text/javascript" src="https://file.lantingshucheng.com/blog/v3/static/scripts/gitalk.min.js"></script>

<script src="/js/main.js"></script>
<!-- search -->

<!-- Google Analytics -->

<!-- Baidu Analytics -->

    <script type="text/javascript">
        var _hmt = _hmt || [];
        (function() {
            var hm = document.createElement("script");
            hm.src = "https://hm.baidu.com/hm.js?7851ca7a86be957be994acb77639a5be";
            var s = document.getElementsByTagName("script")[0];
            s.parentNode.insertBefore(hm, s);
        })();
    </script>

<!-- Disqus Comments -->


  <script type="text/javascript">
    window.onload = function(){
      if (window.location.href.indexOf('andyliwr.github.io') > -1) {
        var gitalk = new Gitalk({
          clientID: 'ad6f70df0c70d2b715f9',
          clientSecret: '40384bee244c1e17dd7c37733d21e9ef669e969c',
          repo: 'Andyliwr.github.io',
          owner: 'Andyliwr',
          admin: ['Andyliwr'],
          id: md5(location.pathname),
          distractionFreeMode: 'true'
        })
        gitalk.render('gitalk_thread')
      }
    }
  </script>


